Routing devices within a network, often referred to as routers, maintain routing information bases (RIBs) of routing information that describe available routes through the network. Upon receiving an incoming packet, the router examines information within the packet and forwards the packet in accordance with the routing information. In order to maintain an accurate representation of the network, routers exchange routing information in accordance with one or more defined routing protocols.
When using a link-state interior gateway protocol (IGP), such as the Open Shortest Path First protocol (OSPF) or Intermediate System to Intermediate System protocol (IS-IS), each router possesses information about the complete topology of the network within which it resides. As a network grows large, scaling within the network may be necessary to manage the amount of network topology information exchanged by routers in the network. Link-state IGP, such as IS-IS or OSPF, addresses network scaling issues by hierarchically separating a network into multiple hierarchical regions (e.g., “areas” or “levels”) so as to increase routing scalability. For example, OSPF areas or IS-IS levels may be used to hierarchically partition the network into distinct regions, such as a backbone area that includes core routers, and one or more non-backbone areas. OSPF and IS-IS allow an autonomous system to, for example, be partitioned into different regions so as to increase routing scalability within a routing domain. Any IGP regions within the partitioned network need only maintain link state for the routers within the respective area. In this way, each of the IGP regions may be viewed as a separate routing domain within the partitioned network, and link state information need not generally be exchanged between all of the routers of different regions, thus reducing the link-state information in the RIB maintained by each of the routers.
Using an IGP that employs such hierarchical scaling, each router in a given network region stores both topological and reachability information for only other devices in the same region, and maintains only reachability information for all other regions in the network. In some cases, network scaling may alternatively or additionally be addressed by IGPs by aggregation of network address prefixes. That is, a router carries network addresses in complete form (often referred to as “/32” or host addresses) for routers that are located within the same network region, and maintains aggregated network address prefixes (i.e., less than full network addresses, such as “/16” prefixes) to represent other regions within the network.
One mechanism for carrying network traffic through a network is Multi-protocol Label Switching (MPLS). MPLS works by prefixing a network packet with an MPLS header that contains a stack of one or more “labels.” Label switching routers (LSRs) forward network traffic based on the labels carried by the packets. Using MPLS, the LSRs can distribute labels and establish paths through the network, i.e., Label Switched Paths (LSPs). An LSP defines a distinct path through the network to carry MPLS packets from a source device to a destination device. Each router along an LSP allocates a label and propagates the label to an upstream router along the path for subsequent affixing to network traffic to form MPLS packets to be forwarded along the path. LSRs along the path cooperatively perform MPLS operations to forward the MPLS packets along the established path. A short label associated with a particular LSP is initially affixed to packets that are to travel through the network via the LSP, and that label may be replaced with subsequent labels at each LSR along the path.
A label distribution protocol such as the Label Distribution Protocol (LDP), targeted LDP, or the resource reservation protocol with traffic engineering extensions (RSVP-TE) may be used for distributing labels and establishing LSPs within a network. Using LDP, for example, a router may output control-plane LDP label mapping messages to advertise a label to neighboring routers for subsequent use in sending traffic to a particular destination associated with the advertising router.
LDP requires that network address specified in the LDP label mapping message exactly match a network address contained within the RIB maintained by the router. Therefore, if LDP were used to establish an LSP between LSRs in different IGP areas/levels, the specific (e.g., the exact/32 for IPv4) loopback addresses of all the LSRs are redistributed across all IGP areas. This generally requires “route leaking” between the LSRs (i.e., use of a routing protocol for the exchange of routing information that otherwise would not be exchanged) so that inter-area routes and network addresses are “leaked” into the RIB of each LSR along the LSP. This can greatly expand the size of the RIB maintained by each of the LSR in order to support LDP across IGP areas (routing domains). This can become a barrier to effective network scaling when an IGP is used across multiple areas. For example, use of LDP for MPLS forwarding across IGP regions would otherwise require LSRs within the network to maintain a large amount of routing state, which defeats much of the benefits of IGP scaling by way of hierarchical areas or levels. Moreover, many network service providers regard route leaking as both a scalability issue as well as an operational problem. RSVP-TE supports “hierarchical” LSP creation. However, this technique only reduces the control and data plane state in some of the nodes, and does not reduce the total number of LSPs required, which can be very large (i.e., N*(N−1) LSPs are needed to fully interconnect N nodes in a network.)